Paper 2017/942
On Secure Two-Party Computation in Three Rounds
Prabhanjan Ananth and Abhishek Jain
Abstract
We revisit the exact round complexity of secure two-party computation. While four rounds are known to be sufficient for securely computing general functions that provide output to one party [Katz-Ostrovsky, CRYPTO'04], Goldreich-Krawczyk [SIAM J. Computing'96] proved that three rounds are insufficient for this task w.r.t. black-box simulation. In this work, we study the feasibility of secure computation in three rounds using non-black-box simulation. Our main result is a three-round two-party computation protocol for general functions against adversaries with auxiliary inputs of bounded size. This result relies on a new two round input-extraction protocol based on succinct randomized encodings. We also provide a partial answer to the question of achieving security against non-uniform adversaries. Assuming sub-exponentially secure iO and one-way functions, we rule out three-round protocols that achieve polynomial simulation-based security against the output party and exponential indistinguishability-based security against the other party.
Metadata
- Available format(s)
-
PDF
- Publication info
- A major revision of an IACR publication in TCC 2017
- Keywords
- secure computationround complexity
- Contact author(s)
-
prabhanjan va @ gmail com
abhishek @ cs jhu edu - History
- 2017-09-27: revised
- 2017-09-27: received
- See all versions
- Short URL
- https://ia.cr/2017/942
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2017/942,
author = {Prabhanjan Ananth and Abhishek Jain},
title = {On Secure Two-Party Computation in Three Rounds},
howpublished = {Cryptology {ePrint} Archive, Paper 2017/942},
year = {2017},
url = {https://eprint.iacr.org/2017/942}
}
